package org.lql.algo.codecrush.week010;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-30 15:33
 * @description: 889. 根据前序和后序遍历构造二叉树 <a href="https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/">...</a>
 **/
public class ConstructFromPrePost {

	public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
		return build(preorder, 0, preorder.length - 1,
				postorder, 0, postorder.length - 1);
	}

	private TreeNode build(int[] preorder, int preL, int preR,
	                       int[] postorder, int postL, int postR) {
		if (preL > preR) {
			return null;
		}

		TreeNode root = new TreeNode(preorder[preL]);
		if (preL == preR) {
			return root; // 只有一个节点
		}

		// preorder[preL+1] 是左子树的根
		int leftRootVal = preorder[preL + 1];
		int idx = postL;
		while (postorder[idx] != leftRootVal) {
			idx++;
		}
		int leftSize = idx - postL + 1;

		// 划分左右子树
		root.left = build(preorder, preL + 1, preL + leftSize,
				postorder, postL, idx);
		root.right = build(preorder, preL + leftSize + 1, preR,
				postorder, idx + 1, postR - 1);

		return root;
	}
}
